Skip to main content

Reverse Bits

LeetCode 190 | Difficulty: Easy​

Easy

Problem Description​

Reverse bits of a given 32 bits signed integer.

Example 1:

Input: n = 43261596

Output: 964176192

Explanation:

        Integer
        Binary
    
    
        43261596
        00000010100101000001111010011100
    
    
        964176192
        00111001011110000010100101000000

Example 2:

Input: n = 2147483644

Output: 1073741822

Explanation:

        Integer
        Binary
    
    
        2147483644
        01111111111111111111111111111100
    
    
        1073741822
        00111111111111111111111111111110

Constraints:

- `0 <= n <= 2^31 - 2`

- `n` is even.

Follow up: If this function is called many times, how would you optimize it?

Topics: Divide and Conquer, Bit Manipulation

Approach​

Bit Manipulation​

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Solutions​

Solution 1: C# (Best: 56 ms)​

MetricValue
Runtime56 ms
MemoryN/A
Date2018-08-20
Solution
public class Solution {
    public uint reverseBits(uint n) {
        uint result = 0;
    for (int i = 0; i < 32; i++)
    {   
        var end = n & 1;
        n >>= 1;
        result <<=1;
        result |= end;      
    }
    return result;
    }
}
📜 1 more C# submission(s)

Submission (2018-08-20) — 64 ms, N/A​

public class Solution {
    public uint reverseBits(uint n) {
        uint result = 0;
    for (int i = 0; i < 32; i++)
    {   
        var end = n & 1;
        n >>= 1;
        result <<=1;
        result |= end;      
    }
    return result;
    }
}

Complexity Analysis​

ApproachTimeSpace
Bit Manipulation$O(n) or O(1)$$O(1)$

Interview Tips​

Key Points
  • Start by clarifying edge cases: empty input, single element, all duplicates.